home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / fish / 001-100 / 001-025 / 014 / dex / hashtbl.c < prev    next >
C/C++ Source or Header  |  1995-03-17  |  11KB  |  467 lines
  1. /************************************************************************
  2.  *                                    *
  3.  *            Copyright (c) 1982, Fred Fish            *
  4.  *                All Rights Reserved                *
  5.  *                                    *
  6.  *    This software and/or documentation is released for public    *
  7.  *    distribution for personal, non-commercial use only.        *
  8.  *    Limited rights to use, modify, and redistribute are hereby    *
  9.  *    granted for non-commercial purposes, provided that all        *
  10.  *    copyright notices remain intact and all changes are clearly    *
  11.  *    documented.  The author makes no warranty of any kind with    *
  12.  *    respect to this product and explicitly disclaims any implied    *
  13.  *    warranties of merchantability or fitness for any particular    *
  14.  *    purpose.                            *
  15.  *                                    *
  16.  ************************************************************************
  17.  */
  18.  
  19.  
  20. /*
  21.  *  FILE
  22.  *
  23.  *    hashtbl.c   generic hash table utility routines
  24.  *
  25.  *  KEYWORDS
  26.  *
  27.  *    hash table
  28.  *    hash function
  29.  *
  30.  *  DESCRIPTION
  31.  *
  32.  *    In many programming applications, a need exists for
  33.  *    a relatively simple set of utility routines for
  34.  *    managing a lookup table.  Typically, information
  35.  *    is accessed by a single "key", such as a person's
  36.  *    name, a programming variable character string, etc.
  37.  *
  38.  *    These utility routines provide useful table manipulation
  39.  *    routines for small to medium sized tables.  The method
  40.  *    used is a hash table, with all entries hashing to a
  41.  *    particular value stored in a linked list.
  42.  *
  43.  *    Each table entry points to an arbitrary structure (tbl_data)
  44.  *    defined externally, which contains the actual information
  45.  *    associated with that entry (including the name of the entry).
  46.  *    To keep these routines generic, only pointers to the
  47.  *    structure are manipulated.  Specifically note that the
  48.  *    actual storage associated with the information in each
  49.  *    entry must be allocated external to these routines.
  50.  *
  51.  *  FUNCTIONS
  52.  *
  53.  *    tbl_find   find a table entry and return pointer
  54.  *    tbl_add    add an entry to the table
  55.  *    dump_tbl   dump the hash table for debugging
  56.  *
  57.  *  BUGS
  58.  *
  59.  *    Current hash function is very primitive and may give
  60.  *    a very unbalanced table for some classes of strings.
  61.  *
  62.  *  AUTHOR
  63.  *
  64.  *    Fred Fish
  65.  *
  66.  */
  67.  
  68. #include <stdio.h>
  69. #include "hashtbl.h"
  70.  
  71. struct tbl_entry {        /* Structure for each table entry */
  72.     char *name;            /* Table entry name */
  73.     struct tbl_data *tdp;    /* Structure defined in "hashtbl.h" */
  74.     struct tbl_entry *next;    /* Next entry with same hash value */
  75. };
  76.  
  77. #define SCR_WIDTH 80        /* Screen width for table dump */
  78. #define SMATCH 0        /* Value when strings are same */
  79.  
  80. extern int debug;        /* Debug flag */
  81. extern int trace;        /* Trace flag */
  82.  
  83. static struct tbl_entry *hash_table[HASH_SIZE];
  84.  
  85.  
  86. /*
  87.  *  FUNCTION
  88.  *
  89.  *    tbl_find   find a table entry and return struct pointer
  90.  *
  91.  *  KEY WORDS
  92.  *
  93.  *    table lookup
  94.  *    hash table
  95.  *
  96.  *  SYNOPSIS
  97.  *
  98.  *    struct tbl_data *tbl_find(name)
  99.  *    char *name;
  100.  *
  101.  *  DESCRIPTION
  102.  *
  103.  *    Given the name of an entry in the table, this routine
  104.  *    attempts to look it up and return a pointer to it's
  105.  *    associated structure.   If no entry of the specified
  106.  *    name is found then a NULL is returned.
  107.  *
  108.  *    The table is structured as a number of linked lists 
  109.  *    with the pointer to the first link stored in a hash table.
  110.  *    Each entry in a specific linked list hashes to the same
  111.  *    value.  For example:
  112.  * 
  113.  *            HASH TABLE      LINKED LIST
  114.  *            ----------    -----------------------
  115.  *
  116.  *               .
  117.  *               .
  118.  *              NULL
  119.  *              "12"       =>    name1 => name2 => name3 
  120.  *              NULL
  121.  *              "31"       =>    name4
  122.  *              "32"       =>    name5 => name6
  123.  *               .
  124.  *               .
  125.  *            
  126.  *  RETURNS
  127.  *
  128.  *    Returns pointer to structure if the entry is found.  Returns
  129.  *    NULL if no entry has specified name.
  130.  *
  131.  */
  132.  
  133. /*
  134.  *  PSEUDO CODE
  135.  *
  136.  *    Begin tbl_find.
  137.  *        If pointer to name is not NULL then
  138.  *            Get pointer to first entry for current hash value.
  139.  *            While there is a table entry to test for a name match
  140.  *                If the names match then
  141.  *                    Return pointer to the structure for the entry.
  142.  *                Else
  143.  *                    Lookup the next table entry for the hash value.
  144.  *                End if
  145.  *            End while
  146.  *        End if
  147.  *        Return NULL for no entry found.
  148.  *    End tbl_find.
  149.  *
  150.  */
  151.  
  152. struct tbl_data *tbl_find(name)
  153. char *name;
  154. {
  155.     struct tbl_entry *lookup;
  156.  
  157.     if(trace) {printf("beginning table_find\n");}
  158.     if (name != NULL) {
  159.         lookup = hash_table[hash(name)];
  160.         while (lookup != NULL) {
  161.         if (strcmp(lookup->name,name) == SMATCH) {
  162.             return (lookup->tdp);
  163.         } else {
  164.             lookup = lookup->next;
  165.         }
  166.     }
  167.     }
  168.     return ((struct tbl_data *)NULL);
  169. }
  170.  
  171. /*
  172.  *  FUNCTION
  173.  *
  174.  *    tbl_add   add an entry to the table
  175.  *
  176.  *  KEY WORDS
  177.  *
  178.  *    hash table
  179.  *    table insertions
  180.  *
  181.  *  SYNOPSIS
  182.  *
  183.  *    struct tbl_data *tbl_add(new_data)
  184.  *    struct tbl_data *new_data;
  185.  *
  186.  *  DESCRIPTION
  187.  *
  188.  *    This routine is responsible for adding entries to the table.
  189.  *    Note that to avoid any possibility of duplicate entries, 
  190.  *    tbl_add first calls tbl_find to see if an entry exists.
  191.  *    This usually results in duplication of effort since most
  192.  *    calls to tbl_add are already preceded by a call to
  193.  *    tbl_find.  However duplicate entries are a serious matter
  194.  *    and every effort should be made to avoid them.
  195.  *
  196.  *  RETURNS
  197.  *
  198.  *    Returns pointer to the table data structure if add is
  199.  *    successful, NULL otherwise (such as duplicate entry).
  200.  *
  201.  */
  202.  
  203. /*
  204.  *  PSEUDO CODE
  205.  *
  206.  *    Begin tbl_add.
  207.  *        If the pointer to the entry name is not valid then
  208.  *            Return a NULL.
  209.  *        Else if the entry already exists then
  210.  *        Return a NULL.
  211.  *        Else
  212.  *            Allocate new memory for the new table entry.
  213.  *        If allocation fails then
  214.  *            Return a NULL.
  215.  *        Else
  216.  *                Save pointer to the entry name in the table entry.
  217.  *                Save the structure pointer in the table entry.
  218.  *                Initialize the pointer to the next table entry to NULL.
  219.  *                Compute the hash value for the entrie's name.
  220.  *                If the hash table currently contains no entry for value
  221.  *                    Start a new table entry chain with hash value.
  222.  *                Else
  223.  *                    While there is another link in the current chain
  224.  *                        Skip over current and go to the next link.
  225.  *                    End while
  226.  *                    Add the new link at the end of the chain.
  227.  *                End if
  228.  *            Return pointer to struct (for success).
  229.  *        End if
  230.  *        End if
  231.  *    End tbl_add
  232.  *
  233.  */
  234.  
  235.  
  236. struct tbl_data *tbl_add(new_data)
  237. struct tbl_data *new_data;
  238. {
  239.     struct tbl_entry *new, *scan;
  240.     int hash_value;
  241.     char *get_memory();
  242.  
  243.     if(trace) {printf("beginning tbl_add\n");}
  244.     if (new_data->name == NULL) {
  245.     return((struct tbl_data *)NULL);
  246.     } else if (tbl_find(new_data->name) != NULL) {
  247.     return((struct tbl_data *)NULL);
  248.     } else {
  249.         new = (struct tbl_entry *) get_memory(sizeof(struct tbl_entry));
  250.     if (new == NULL) {
  251.         return((struct tbl_data *)NULL);
  252.     } else {
  253.         new->name = new_data->name;
  254.         new->tdp = new_data;
  255.         new->next = NULL;
  256.         hash_value = hash(new->name);
  257.         if ((scan = hash_table[hash_value]) == NULL) {
  258.             hash_table[hash_value] = new;
  259.         } else {
  260.             while (scan->next != NULL) {
  261.             scan = scan->next;
  262.             }
  263.             scan->next = new;
  264.         }
  265.         return(new_data);
  266.     }
  267.     }
  268. }
  269.  
  270. /*
  271.  *  FUNCTION
  272.  *
  273.  *    hash   compute hash value for a string
  274.  *
  275.  *  KEY WORDS
  276.  *
  277.  *    hash table
  278.  *    hash function
  279.  *
  280.  *  SYNOPSIS
  281.  *
  282.  *    int hash(string)
  283.  *    char *string;
  284.  *
  285.  *  DESCRIPTION
  286.  *
  287.  *    Takes an input string and returns a hash value
  288.  *    for that string.  Note that the algorithm used has the merit
  289.  *    of extreme simplicity but is by no means the best.
  290.  *
  291.  *  RETURNS
  292.  *
  293.  *    Hash value of string.
  294.  *
  295.  */
  296.  
  297. /*
  298.  *  PSEUDO CODE
  299.  *
  300.  *    Begin hash.
  301.  *        Initialize hash value to be zero.
  302.  *        While there is a character left in input string.
  303.  *            Sum the character's value into the hash value.
  304.  *        End while
  305.  *        Return the value (modulo the hash table size).
  306.  *    End hash.
  307.  *
  308.  */
  309.  
  310. static int hash(string)
  311. char *string;
  312. {
  313.     register int hash_value;
  314.  
  315.     if(trace) {printf("beginning hash\n");}
  316.     hash_value = 0;
  317.     while (*string != NULL) {
  318.     hash_value += *string++;
  319.     }
  320.     hash_value %= HASH_SIZE;
  321.     return (hash_value);
  322. }
  323.  
  324. /*
  325.  *  FUNCTION
  326.  *
  327.  *    dump_tbl   dump hash table for debugging purposes
  328.  *
  329.  *  KEY WORDS
  330.  *
  331.  *    hash table
  332.  *
  333.  *  SYNOPSIS
  334.  *
  335.  *    dump_tbl()
  336.  *
  337.  *  DESCRIPTION
  338.  *
  339.  *    Prints the table contents on the standard output
  340.  *    in the format:
  341.  *
  342.  *        nnn:    name : name : name : name ...
  343.  *
  344.  *    Where "nnn" is the hash value (index into the table) and
  345.  *    "name" is the name of an entry.  The names are printed
  346.  *    in the same order they are encountered in the linked list, and
  347.  *    all have the same hash value.
  348.  *
  349.  *    Note that the distribution of names can give some indication of
  350.  *    the suitability of the particular hash function used.
  351.  *
  352.  */
  353.  
  354. /*
  355.  *  PSEUDO CODE
  356.  *
  357.  *    Begin dump_tbl
  358.  *        For each hash table entry in the table
  359.  *        If the hash table entry points to a chain then
  360.  *            Initialize output buffer with hash value output.
  361.  *            For each entry in the linked list chain
  362.  *            If adding name would overflow buffer then
  363.  *                Print the buffer.
  364.  *                Reinitialize buffer for additional line.
  365.  *            End if
  366.  *            Add entry name to buffer
  367.  *            End for
  368.  *            Print the buffer.
  369.  *        End if
  370.  *        End for
  371.  *    End dump_tbl
  372.  *
  373.  */
  374.  
  375. dump_tbl()
  376. {
  377.     char buffer[SCR_WIDTH];
  378.     int hash_index;
  379.     struct tbl_entry *tp;
  380.  
  381.     for (hash_index=0; hash_index<HASH_SIZE; hash_index++) {
  382.     if (hash_table[hash_index] != NULL) {
  383.         sprintf(buffer,"%d ",hash_index);
  384.         for (tp=hash_table[hash_index]; tp != NULL; tp=tp->next) {
  385.         if ((strlen(tp->name) + strlen(buffer) + 4) > SCR_WIDTH) {
  386.             printf("%s\n",buffer);
  387.             sprintf(buffer,"\t");
  388.         }
  389.         strcat(buffer," : ");
  390.         strcat(buffer,tp->name);
  391.         }
  392.             printf("%s\n",buffer);
  393.     }
  394.     }
  395. }
  396.  
  397. /*
  398.  *  FUNCTION
  399.  *
  400.  *    get_memory   allocate more main memory and zero it
  401.  *
  402.  *  KEY WORDS
  403.  *
  404.  *    memory allocator
  405.  *
  406.  *  SYNOPSIS
  407.  *
  408.  *    char *get_memory(how_much)
  409.  *    unsigned int how_much;
  410.  *
  411.  *  DESCRIPTION
  412.  *
  413.  *    This routine is responsible for all memory allocation 
  414.  *    requests.  If the amount of memory requested cannot be 
  415.  *    allocated for any reason, an error message is printed
  416.  *    and NULL is returned.
  417.  *
  418.  *    To avoid any question about the contents of the newly
  419.  *    allocated memory (some systems zero it, others don't),
  420.  *    we explicitly zero the memory.
  421.  *
  422.  *  RETURNS
  423.  *
  424.  *    Pointer to allocated memory or NULL if memory allocation
  425.  *    fails.
  426.  *
  427.  */
  428.  
  429. /*
  430.  *  PSEUDO CODE
  431.  *
  432.  *    Begin get_memory
  433.  *        Attempt to allocate the requested number of bytes.
  434.  *        If allocation attempt failed then
  435.  *            Print memory allocation failure message.
  436.  *        Return NULL.
  437.  *        Else
  438.  *            For each byte in new memory.
  439.  *                Zero the byte.
  440.  *            End for
  441.  *        End if
  442.  *        Return pointer to the memory which was allocated.
  443.  *    End get_memory
  444.  *
  445.  */
  446.  
  447. char *get_memory(how_much)
  448. unsigned int how_much;
  449. {
  450.     char *memory, *mem;
  451.     char *malloc();
  452.     int count;
  453.  
  454.     if(trace) {printf("beginning get_memory\n");}
  455.     memory = malloc(how_much);
  456.     if (memory == NULL) {
  457.     fprintf(stderr,"?hashtbl: unable to allocate more memory!\n");
  458.     return(NULL);
  459.     } else {
  460.     mem = memory;
  461.     for (count=0; count<how_much; count++) {
  462.         *mem++ = 0;
  463.     }
  464.     }
  465.     return(memory);
  466. }
  467.